﻿// 2761. 和等于目标值的质数对.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>

using namespace std;
/*
https://leetcode.cn/problems/prime-pairs-with-target-sum/description/

给你一个整数 n 。如果两个整数 x 和 y 满足下述条件，则认为二者形成一个质数对：

1 <= x <= y <= n
x + y == n
x 和 y 都是质数
请你以二维有序列表的形式返回符合题目要求的所有 [xi, yi] ，列表需要按 xi 的 非递减顺序 排序。如果不存在符合要求的质数对，则返回一个空数组。

注意：质数是大于 1 的自然数，并且只有两个因子，即它本身和 1 。



示例 1：
输入：n = 10
输出：[[3,7],[5,5]]
解释：在这个例子中，存在满足条件的两个质数对。
这两个质数对分别是 [3,7] 和 [5,5]，按照题面描述中的方式排序后返回。

示例 2：
输入：n = 2
输出：[]
解释：可以证明不存在和为 2 的质数对，所以返回一个空数组。


提示：
1 <= n <= 106
*/


class Solution {
public:
    int primes[100000], cnt;     // primes[]存储所有素数
    vector<int> st;         // st[x]存储x是否被筛掉
    void get_primes(int n)
    {
        memset(primes,0,sizeof primes);
        cnt = 0;
        st.resize(n+10);
        for (int i = 2; i <= n; i++)
        {
            if (!st[i]) primes[cnt++] = i;
            for (int j = 0; primes[j] <= n / i; j++)
            {
                st[primes[j] * i] = true;
                if (i % primes[j] == 0) break;
            }
        }
    }

    vector<vector<int>> findPrimePairs(int n) {
        get_primes(n);
        vector<vector<int>> ans;
        for (int i = 0; i <= cnt; i++) {
            if (primes[i] > n/2) break;
            int find = n - primes[i];

            int l = 0; int r = cnt;
            while (l < r) {
                int mid = l + r >> 1;
                if (primes[mid] >= find) r = mid;
                else l = mid + 1;
            }

            if (primes[l] == find) {
                ans.push_back({ primes[i],primes[l] });
            }
        }

        return ans;
    }
};


int main()
{
    Solution s;
    s.findPrimePairs(10);
}

